package leetcode_动态规划._02矩阵路径;

import java.util.Arrays;

/**
 * 不同路径
 * 算法：
 *   跟 64 一样，由于只能向右或者向下
 *   所以第一行和第一列只有一种走法
 */
public class _62 {

    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] = dp[j - 1] + dp[j];
            }
        }
        return dp[n - 1];
    }
}
